/*
 * InsertedSort function is used to sort a arry
 * algorithm:First,choose the second number of the array to compare with the first number,
 *           if first>second ,then swap the two numbers, increase the index by step one,compare 
 *           with before number ,then swap if it satisfy the condition
 * time complexity:O(n^2)
 * @author:Yong Ruolan
 * @Date:2015,9,24
 */

public class InsertedSort {
	/*
	 * 直接插入排序
	 */
	public static int[] sort(int[] rawData){
		//long startTime=System.currentTimeMillis();
		for(int i=1;i<rawData.length;i++){
			for(int j=0;j<i;j++){
				if(rawData[j]>rawData[i]){
					int temp=rawData[j];
					rawData[j]=rawData[i];
					rawData[i]=temp;
				}
			}
		}
		//long endTime=System.currentTimeMillis();
		//System.out.println("sort time:"+(endTime-startTime));
		return rawData;
		
	}
	/*
	 * 直接插入排序算法二
	 */
	public static int[] sort2(int[] rawData){
		//long startTime=System.currentTimeMillis();	
		for(int i=1;i<rawData.length-1;i++){
				if(rawData[i]>rawData[i+1]){
					int temp=rawData[i];
					rawData[i]=rawData[i+1];
					rawData[i+1]=temp;
                }
		}
		//long endTime=System.currentTimeMillis();
		
		return rawData;
		
	}
	
	/*
	 * 二分插入排序
	 */
	public static int[] halfSearchSort(int[] rawData){
		//long startTime=System.currentTimeMillis();
		int start=0;
		int end=0;
		int half=0;
		for(int i=1;i<rawData.length;i++){
			for(int j=0;j<i;j++){
				end=i-1;
				half=(start+end)/2;	
				//循环条件的控制：start>0,防止初始步骤的死循环
				while(start<=end&&start>0){
				 if(rawData[j]>rawData[half]){
						start=half+1;
					}
					else if(rawData[j]<rawData[half]){
						end=half-1;
					}else{
						int temp=rawData[j+1];
						rawData[j+1]=rawData[i];
						rawData[i+1]=temp;
					}
					System.out.println("half="+half);					
				}
			
			}
		}
	//	long endTime=System.currentTimeMillis();
	//	System.out.println("half sort time:"+(endTime-startTime));
		return rawData;
	}
	public static void main(String[] args) {
		int[] a={4,3,6,2,7,5,9,1,10,23,-7,11,45,11,23,0,-2,-1,100,15};
		int[] b=sort(a);
		int[] c=sort2(a);
		int[] d=halfSearchSort(a);
		for(int temp:b)
			System.out.print(temp+"\t");
		System.out.println();
		for(int temp:c)
			System.out.print(temp+"\t");
		System.out.println();
		for(int temp:d)
			System.out.print(temp+"\t");
	}

}
